package LeetCodeHot100TopInterview;

public class Q064_MatrixPathSumMin {
    //矩阵最小路径和
    //只能走右或走下
    public int minPathSum(int[][] grid) {
        int L1 = grid.length - 1;
        int L2 = grid[0].length - 1;
        int[][] dp = new int[L1 + 1][L2 + 1];
        dp[L1][L2] = grid[L1][L2];
        //最后一列
        for (int i = L1 - 1; i > -1 ; i--) {
            dp[i][L2] = grid[i][L2] + dp[i + 1][L2];
        }
        for (int i = L2 - 1; i > -1 ; i--) {
            dp[L1][i] = grid[L1][i] + dp[L1][i + 1];
        }
        for (int i = L1 - 1; i > -1; i--) {
            for (int j = L2 - 1; j > -1 ; j--) {
                dp[i][j] = grid[i][j] + Math.min(dp[i + 1][j], dp[i][j + 1]);
            }
        }

        return dp[0][0];
    }

    public static void main(String[] args) {
        Q064_MatrixPathSumMin fun = new Q064_MatrixPathSumMin();
        fun.minPathSum(null);
    }
}
